《剑指offer》 16.数值的整数次方

剑指offer
留言

note:快速幂是一个常用经典需要好好掌握的知识点。另外此题中如何处理指数为负数的情况的方法值得总结

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

1
2
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

1
2
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

1
2
3
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • $-100.0 < x < 100.0$
  • $-2^{31} <= n <= 2^{31}-1$
  • $-10^4 <= x^n <= 10^4$

方法 快速幂算法

思路

快速幂的思想在前面几道题也有所记录，其实本质它是一种二分的思想，将复杂度为$O(n)$的循环求余的方法，复杂度精简到了$O(logn)$。

根据二分推导$x^n = x^{n/2}\times x^{n/2}=(x^2)^{n/2}$，我们的指数显然存在两种情况：

  • n为偶数：$x^n = (x^2)^{n//2}$（//表示整除）
  • n为奇数:$x^n=x(x^2)^{n//2}$

据此，我们可以通过循环$x=x^2$操作，每次幂都会从$n$降至$n//2$，直至n变为0；

那我们可以用一个变量存储出现奇数时单独计算多出的一项$x$，从而让我们的循环可以持续进行。

判断奇数偶数的办法可以用求余，也可以用位运算$n\&1$。

此题另外一个有趣的地方在于对于负指数的处理，很简单的解决方法就是将指数转换为$(-1)(-n)$，也就可以将$x^n$转换为$x^{-1}x^{-n}$。

还有一个问题就是由于n的范围在$[-2^{31},2^{31}-1]$。所以存在当$n=-2^{31}$的时候，直接取反会溢出的情况，所以最好将n转换为long long型参与计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    double myPow(double x, int n) {
        if(x==0)
            return 0;
        long long a = n;
        double res = 1;
        if(a<0){
            x = 1/x;
            a = -a;    
        }

        while(a){
            if(a%2==1) res = res*x;
            x = x*x;
            a/=2;
        }

        return res;
    }
};

复杂度分析

  • 时间复杂度$O(logn)$。快速幂的二分思想，让我们的时间复杂度变为$logN$
  • 空间复杂度$O(1)$。